package Algorithm.A1;
/*
* @Author :lcy
* @Description :最小生成树的prim算法
* 原理：
1、我们选择一个顶点，也就是选择了一个树。
2、向外找权重最小的边，这样这棵树就有了两个顶点
3、再以这两个顶点向外找权重最小的边，依次循环，知道所有顶点收到树里
* @Date 2021/11/25 16:20
*/

import java.util.ArrayList;
import java.util.List;

public class Prim {
    public static void main(String[] args) {
        float m = Float.MAX_VALUE;
        float[][] weight = {
                {0, 0, 0, 0, 0, 0, 0},
                {0, m, 6, 1, 5, m, m},
                {0, 6, m, 5, m, 3, m},
                {0, 1, 5, m, 5, 6, 4},
                {0, 5, m, 5, m, m, 2},
                {0, m, 3, 6, m, m, 6},
                {0, m, m, 4, 2, 6, m}};

        prim(weight);
    }

    public static void prim(float[][] weight) {
        int vNum = weight.length - 1; //取二维数组边长-1，因为后面初始化newList时会先添加一个点

        List<Integer> newList = new ArrayList<>(); //新集合存放已经找到的点
        List<Integer> oldList = new ArrayList<>(); //旧集合存放还未找到的点

        //初始化oldList，直接赋值顶点号
        for (int i = 1; i <= 6; i++) {
            oldList.add(i);
        }
        //初始化newList，这里是从1点开始遍历
        newList.add(1);

        //将oldList中1号点除去
        oldList.remove(new Integer(1));

        while (newList.size() != vNum) {
            float min = Float.MAX_VALUE;//初始化min，将它定义成一个最大的浮点数
//            System.out.println(min);
            int oldIndex = 1; //找到最小边时旧集合的点
            int newIndex = 1; //找到最小边时新集合的点

            for (int i = 0; i < newList.size(); i++) {  //寻找新集合到旧集合的最小权值的边
                int index = newList.get(i);//获取newList中的节点

                for (int j = 0; j < oldList.size(); j++) {
                    int k = oldList.get(j);//获取oldList中的节点

                    if (min > weight[index][k]) { //记录最小边的相关信息，用于打印
                        min = weight[index][k];
                        oldIndex = k;
                        newIndex = index;
                    }
                }
            }
            System.out.println(newIndex + "->" + oldIndex + ": " + min);
//            weight[newIndex][oldIndex] = Float.MAX_VALUE; //找过的最小边置为最大值
//            weight[oldIndex][newIndex] = Float.MAX_VALUE; //对称边也要置为最大值
            newList.add(oldIndex);
            oldList.remove(new Integer(oldIndex));
        }
    }
}


